package demo1;

public class DynamicPlanningPractise {
    /**
     * 删除并获得点数
     * 时间复杂度O(n+max)
     * 空间复杂度O(max)*/
    public int deleteAndEarn(int[] nums) {
        //预处理
        int max = nums[0];
        for(int x:nums)
            if(x>max)
                max = x;
        int[] array = new int[max+1];
        int n = array.length;
        for(int i = 0; i < nums.length; i++)
            array[nums[i]] += nums[i];

        //1 创建dp表
        int[] f = new int[n];
        int[] g = new int[n];
        //2 初始化
        f[0] = array[0];
        //3 填表
        for(int i = 1; i < n; i++) {
            f[i] = g[i-1]+array[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        //4 返回值
        return Math.max(f[n-1],g[n-1]);
    }

    /**
     * 粉刷房子
     * 时间复杂度O（n）
     * 空间复杂度O（n）*/
    public int minCost(int[][] costs) {
        /**
         状态表示：dp[i]表示，当以i位置为结尾时，粉刷完所有房子的最小成本
         但是在本题中，当处于i位置时还有三种状态，分别是：
         0 i处房子被粉刷成红色
         1 i处房子被粉刷成蓝色
         2 i处房子被粉刷成绿色
         故需要定义三种状态表示方法：
         red[] + blue[] + green

         状态转移方程（仅以i处房子被刷成红色为例）：由题和状态表示可得：
         red[i]代表当以i位置为结尾时，粉刷完所有房子的最小成本，且i位置房屋为红色
         故red【i-1】位置必定不是红色，而为了使得red【i】为最小成本，需要使得red【i-1】也为最小成本，即是：
         Math.min(blue[i-1],green[i-1]) + costs[i][0] = red[i]
         即是粉刷i处房屋为红色所需的成本 + 前i-1粉刷的最低成本，其它同理

         初始化：
         虚拟位置法，注意虚拟位置的赋值和下标映射关系

         填表顺序：
         从左到右，三个状态表同时填写

         返回值：
         返回三个状态表 n 位置的最小值
         */

        int n = costs.length;
        //1 创建dp表
        int[] red = new int[n+1];
        int[] blue = new int[n+1];
        int[] green = new int[n+1];
        //2 初始化 -由于状态转移方程为取【i-1】下标处的最小值，为了不影响填表的准确性，故虚拟位置赋值为0（不操作即为0）
        //3 填表
        for(int i = 1; i <= n; i++) {
            red[i] = Math.min(blue[i-1],green[i-1]) + costs[i-1][0];
            blue[i] = Math.min(green[i-1],red[i-1]) + costs[i-1][1];
            green[i] = Math.min(red[i-1],blue[i-1]) + costs[i-1][2];
        }
        //4 返回值
        return Math.min(Math.min(red[n],blue[n]),green[n]);
    }

}
